A random access machine (RAM) is a simple model of computation. Its memory consists of an unbounded sequence of registers. Each of the registers may hold an integer value. The control unit of a RAM holds a program, i.e. a numbered list of statements. The program counter (PC) determines which statement is to be executed next. A RAM-program is executed while in each work cycle, the RAM executes one statement of the program. The program counter specifies the number of the statement that is to be executed.
To run a program in the RAM, it is required to:
define the program, i.e. the exact list of statements;
define starting values for the registers (the initial input);
define starting values for the program counter (usually, starting with the first statement).
Secure and private computations over RAM are preferred over computations with circuits or Turing machines. Secure and private RAM executions become more and more important in the scope avoiding information leakage when executing programs over a single computer as well as over the clouds.
Cloud computing (for the delivery of hosted services over the Internet, which enables companies to consume compute resources as a utility, rather than having to build and maintain computing infrastructures in-house) provides cost-efficient and flexible shared infrastructure and computational services on demand for various customers who need to store and operate on a huge amount of data. Until now, there are various services providers such as Amazon and Google who offer platforms, software, and storage outsourcing applications. Much attention has been paid to these platforms due to the potential benefits and business opportunities that clouds could bring. However, cloud computing also introduces security and privacy risks for the clients. For example, some of the cloud providers are not perfectly reliable and are vulnerable to network attacks and data leakage. Furthermore, even a single computer with the same cloud organization is untrustworthy.
There are possible attacks on a single computer, during which information is copied from the bus of the computer and sent to an adversary. Therefore, it is extremely important that a server will process unrevealed programs over unrevealed data, in information theoretical secure manner.
One of the most important requirements of the cloud clients is to process their data in a confidential way. Several techniques are applied to address data storage privacy and security computation on clouds. Among these studies, security in evaluating a Random Access Machine (RAM) program is an important task, since many modern algorithms are operating on the von Neumann RAM architecture (a computer architecture for an electronic digital computer with parts consisting of a processing unit containing an arithmetic logic unit and processor registers, a control unit containing an instruction register and program counter, a memory to store both data and instructions, external mass storage, and input and output mechanisms).
There are mainly two existing ways for secure computation of RAM programs. The first way, is to convert a RAM (one shot) program into circuits and the second is to use oblivious RAM (a data encryption tool where the access pattern is independent of the inputs to the algorithm so that it hides not only the data but also the associated algorithms and executed operations, it works by). Oblivious RAM schemes are preferred as they can implement a never ending program (such as an operating system and) there is no need to convert the program into a binary circuit, which leads to a huge blowup in program size and its running time.
Even though the proposed solutions for secure RAM evaluation can address various privacy challenges including two-party, multiparty or large-scale computation against semi-honest or malicious adversaries, they all assume that the processors used by clouds are trustworthy. Thus, in these proposed solutions, the CPU has to decrypt the input data before processing and then encrypt the output data again. During these years, the semiconductor design and fabrication process became global, integrated circuits tend to be increasingly vulnerable to malicious activities and alterations. An adversary can introduce a special hardware Trojan, designed to disable or destroy a system in the future, or leak confidential information. Similar attack has already been demonstrated, where a specially designed Trojan (malicious computer program) in the CPU revealed sensitive information to the adversary.
A client wishing to run a program on the clouds does not want to reveal any information about both the program and the data. The cloud with untrusted hardware that listens to the bus may extract information on the internal activity of the processor.
Unfortunately, none of the protocols that decrypt data prior to processing and manipulating the data can avoid information leakage when the adversary acts within the hardware. Thus, there is a need to execute an encrypted program on encrypted data without decrypting neither the program nor the data. In order to protect privacy, a straightforward approach is to execute the encrypted instructions in the clouds processors directly.
Fully Homomorphic Encryption (FHE—a cryptosystem that supports arbitrary computation on ciphertexts, which enables the construction of programs for any desirable functionality, which can be run on encrypted inputs to produce an encryption of the result. Since such a program need never decrypt its inputs, it can be run by an untrusted party without revealing its inputs and internal state. The existence of an efficient and fully homomorphic cryptosystem would have great practical implications in the outsourcing of private computations, for instance, in the context of cloud computing) is a way to achieve this goal. However, the main problem is that the proposed scheme caused high overhead of computation, which make FHE less practical. Moreover, Gentry's scheme relied on the hardness assumptions on ideal lattices which is only computationally secure, rather than key-less information that is information theoretical secure.
It is therefore an object of the present invention, to provide a distributed scheme for executing RAM programs without revealing any information regarding the computation.
It is another object of the present invention, to provide a distributed scheme for executing RAM programs without revealing any information regarding the program, the data and the result.
It is yet another object of the present invention, to provide a distributed scheme for computing RAM programs which is information theoretic secure RAM execution of perfectly unrevealed programs.
It is still another object of the present invention, to provide a distributed scheme for computing RAM programs which is compatible with big data that is stored in a secret sharing fashion over the clouds, without reconstructing the data from the shares.
Other objects advantages of the present invention will become clear as the description proceeds.